package com.scqzy.shengchunqiang.sword2offer.day20;

/**
 * @Description: 剑指 Offer 33. 二叉搜索树的后序遍历序列
 * @Author 盛春强
 * @Date 2021/8/27 23:13
 */
public class VerifyPostorder {
    public boolean verifyPostorder(int[] postorder) {
        return isPostOrder(postorder, 0, postorder.length - 1);
    }

    private boolean isPostOrder(int[] postorder, int left, int right) {
        if (left >= right) {
            return true;
        }
        int i = left;
        while (postorder[i] < postorder[right]) {
            i++;
        }
        int mid = i;
        while (postorder[i] > postorder[right]) {
            i++;
        }
        return i == right && isPostOrder(postorder, left, mid - 1) && isPostOrder(postorder, mid, right - 1);
    }
}
